home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / libg_261.zip / libg_261 / libg++ / src / gen / PHPQ.ccP < prev    next >
Text File  |  1994-05-20  |  7KB  |  340 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /* 
  3. Copyright (C) 1988 Free Software Foundation
  4.     written by Dirk Grunwald (grunwald@cs.uiuc.edu)
  5.     adapted for libg++ by Doug Lea (dl@rocky.oswego.edu)
  6.  
  7. This file is part of the GNU C++ Library.  This library is free
  8. software; you can redistribute it and/or modify it under the terms of
  9. the GNU Library General Public License as published by the Free
  10. Software Foundation; either version 2 of the License, or (at your
  11. option) any later version.  This library is distributed in the hope
  12. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  13. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  14. PURPOSE.  See the GNU Library General Public License for more details.
  15. You should have received a copy of the GNU Library General Public
  16. License along with this library; if not, write to the Free Software
  17. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  18. */
  19.  
  20.  
  21. #ifdef __GNUG__
  22. #pragma implementation
  23. #endif
  24. #include <limits.h>
  25. #include "<T>.PHPQ.h"
  26.  
  27. //
  28. //    This defines a Pairing Heap structure
  29. //
  30. //    See ``The Pairing Heap: A New Form of Self-Adjusting Heap''
  31. //    Fredman, Segdewick et al,
  32. //    Algorithmica (1986) 1:111-129
  33. //
  34. //    In particular, this implements the pairing heap using the circular
  35. //    list.
  36. //
  37. //
  38.  
  39. <T>PHPQ::<T>PHPQ(int sz)
  40. {
  41.   storage = 0;
  42.   root = 0;
  43.   count = 0;
  44.   size = 0;
  45.   prealloc(sz);
  46. }
  47.  
  48. <T>PHPQ::<T>PHPQ(<T>PHPQ& a)
  49. {
  50.   storage = 0;
  51.   root  = 0;
  52.   count = 0;
  53.   size = 0;
  54.   prealloc(a.size);
  55.   for (Pix i = a.first(); i != 0; a.next(i)) enq(a(i));
  56. }
  57.  
  58.  
  59. void <T>PHPQ::prealloc(int newsize)
  60. {
  61.   ++newsize; // leave a spot for freelist
  62.   if (size != 0)
  63.   {
  64.     int news = size;
  65.     while (news <= newsize) news = (news * 3) / 2;
  66.     newsize = news;
  67.   }
  68.   // see if indices are OK
  69.   <T>PHPQNode test;
  70.   test.sibling = 0;
  71.   test.sibling = ~test.sibling;
  72.   if ((unsigned long)newsize > (unsigned long)(test.sibling))
  73.     error("storage size exceeds index range");
  74.  
  75.   if (storage == 0)
  76.   {
  77.     storage = new <T>PHPQNode[size = newsize];
  78.     for (int i = 0; i < size; ++i) 
  79.     {
  80.       storage[i].sibling = i + 1;
  81.       storage[i].valid = 0;
  82.     }
  83.     storage[size-1].sibling = 0;
  84.   }
  85.   else
  86.   {
  87.     <T>PHPQNode* newstor = new <T>PHPQNode[newsize];
  88.     for (int i = 1; i < size; ++i)
  89.       newstor[i] = storage[i];
  90.     delete [] storage;
  91.     storage = newstor;
  92.     for (i = size; i < newsize; ++i) 
  93.     {
  94.       storage[i].sibling = i + 1;
  95.       storage[i].valid = 0;
  96.     }
  97.     storage[newsize-1].sibling = 0;
  98.     storage[0].sibling = size;
  99.     size = newsize;
  100.   }
  101. }
  102.  
  103.  
  104. void <T>PHPQ::clear()
  105. {
  106.   for (int i = 0; i < size; ++i) 
  107.   {
  108.     storage[i].sibling = i + 1;
  109.     storage[i].valid = 0;
  110.   }
  111.   storage[size-1].sibling = 0;
  112.   root = 0;
  113.   count = 0;
  114. }
  115.  
  116. Pix <T>PHPQ::enq(<T&> item)
  117. {
  118.   ++count;
  119.   if (storage[0].sibling == 0)
  120.     prealloc(count);
  121.  
  122.   int cell = storage[0].sibling;
  123.   storage[0].sibling = storage[cell].sibling;
  124.   storage[cell].sibling = 0;
  125.   storage[cell].children = 0;
  126.   storage[cell].item = item;
  127.   storage[cell].valid = 1;
  128.   
  129.   if (root == 0) 
  130.   {
  131.     root = cell;
  132.     return Pix(root);
  133.   }
  134.   else 
  135.   {
  136.     int parent;
  137.     int child;
  138.     
  139.     if (<T>LE(storage[root].item, storage[cell].item))
  140.     {
  141.       parent = root; child = cell;
  142.     } 
  143.     else 
  144.     {
  145.       parent = cell; child = root;
  146.     }
  147.     int popsKid = storage[parent].children;
  148.     
  149.     if (popsKid == 0) 
  150.     {
  151.       storage[parent].children = child;
  152.       storage[child].sibling = child;
  153.     } 
  154.     else 
  155.     {
  156.       int temp = storage[popsKid].sibling;
  157.       storage[popsKid].sibling = child;
  158.       storage[child].sibling = temp;
  159.       storage[parent].children = child;
  160.     }
  161.     root = parent;
  162.     return Pix(cell);
  163.   }
  164. }
  165.  
  166. //
  167. //    Item removal is the most complicated routine.
  168. //
  169. //    We remove the root (should there be one) and then select a new
  170. //    root. The siblings of the root are in a circular list. We continue
  171. //    to pair elements in this list until there is a single element.
  172. //    This element will be the new root.
  173.  
  174. void <T>PHPQ::del_front()
  175. {
  176.   int valid = 0;
  177.   do 
  178.   {
  179.     if (root == 0) return;
  180.     if (valid = storage[root].valid)
  181.       --count;
  182.     storage[root].valid = 0;
  183.     int child = storage[root].children;
  184.     storage[root].sibling = storage[0].sibling;
  185.     storage[0].sibling = root;
  186.  
  187.     if (child == 0)
  188.     {
  189.       root = 0;
  190.       return;
  191.     }
  192.     else 
  193.     {
  194.       while(storage[child].sibling != child) 
  195.       {
  196.         // We have at least two kids, but we may only have
  197.         // two kids. So, oneChild != child, but it is possible
  198.         // that twoChild == child.
  199.         
  200.         int oneChild = storage[child].sibling;
  201.         int twoChild = storage[oneChild].sibling;
  202.  
  203.         // Remove the two from the sibling list
  204.  
  205.         storage[child].sibling = storage[twoChild].sibling;
  206.         storage[oneChild].sibling = 0;
  207.         storage[twoChild].sibling = 0;
  208.         
  209.         int bestChild;
  210.         int worstChild;
  211.     
  212.         if (<T>LE(storage[oneChild].item, storage[twoChild].item))
  213.         {
  214.           bestChild = oneChild; worstChild = twoChild;
  215.         } 
  216.         else 
  217.         {
  218.           bestChild = twoChild; worstChild = oneChild;
  219.         }
  220.         int popsKid = storage[bestChild].children;
  221.         
  222.         if (popsKid == 0) 
  223.         {
  224.           storage[bestChild].children = worstChild;
  225.           storage[worstChild].sibling = worstChild;
  226.         } 
  227.         else 
  228.         {
  229.           int temp = storage[popsKid].sibling;
  230.           storage[popsKid].sibling = worstChild;
  231.           storage[worstChild].sibling = temp;
  232.           storage[bestChild].children = worstChild;
  233.         }
  234.         if (twoChild == child) 
  235.         {
  236.           // We have reduced the two to one, so we'll be exiting.
  237.           child = bestChild;
  238.           storage[child].sibling = child;
  239.         } 
  240.         else 
  241.         {
  242.           // We've removed two siblings, now we need to insert
  243.           // the better of the two
  244.           storage[bestChild].sibling = storage[child].sibling;
  245.           storage[child].sibling = bestChild;
  246.           child = storage[bestChild].sibling;
  247.         }
  248.       }
  249.       root = child;
  250.     }
  251.   } while ( !valid );
  252. }
  253.  
  254. void <T>PHPQ::del(Pix p) 
  255. {
  256.   if (p == 0) error("null Pix");
  257.   int i = int(p);
  258.   if (storage[i].valid)
  259.   {
  260.     if (i == root)
  261.       del_front();
  262.     else
  263.     {
  264.       storage[i].valid = 0;
  265.       --count;
  266.     }
  267.   }
  268. }
  269.  
  270.  
  271. Pix <T>PHPQ::seek(<T&> key)
  272. {
  273.   for (int i = 1; i < size; ++i)
  274.     if (storage[i].valid && <T>EQ(storage[i].item, key))
  275.       return Pix(i);
  276.   return 0;
  277. }
  278.  
  279. Pix <T>PHPQ::first()
  280. {
  281.   for (int i = 1; i < size; ++i)
  282.     if (storage[i].valid)
  283.       return Pix(i);
  284.   return 0;
  285. }
  286.  
  287.  
  288. void <T>PHPQ::next(Pix& p)
  289. {
  290.   if (p == 0) return;
  291.   for (int i = int(p)+1; i < size; ++i)
  292.     if (storage[i].valid)
  293.     {
  294.       p = Pix(i); 
  295.       return;
  296.     }
  297.   p = 0;
  298. }
  299.  
  300. int <T>PHPQ::OK()
  301. {
  302.   int v = storage != 0;
  303.   int n = 0;
  304.   for (int i = 0; i < size; ++i) if (storage[i].valid) ++n;
  305.   v &= n == count;
  306.   v &= check_sibling_list(root);
  307.   int ct = INT_MAX;
  308.   n = 0;
  309.   int f = storage[0].sibling;
  310.   while (f != 0 && ct-- > 0)
  311.   {
  312.     f = storage[f].sibling;
  313.     ++n;
  314.   }
  315.   v &= ct > 0;
  316.   v &= n <= size - count;
  317.   if (!v) error("invariant failure");
  318.   return v;
  319. }
  320.  
  321.  
  322. int <T>PHPQ::check_sibling_list(int t)
  323. {
  324.   if (t != 0)
  325.   {
  326.     int s = t;
  327.     long ct = LONG_MAX;      // Lots of chances to find self!
  328.     do 
  329.     {
  330.       if (storage[s].valid && !check_sibling_list(storage[s].children))
  331.         return 0;
  332.       s = storage[s].sibling;
  333.     } while (ct-- > 0 && s != t && s != 0);
  334.     if (ct <= 0) return 0;
  335.   }
  336.   return 1;
  337. }
  338.  
  339.  
  340.